package org.example.ch04;

import org.example.ch04.tree.ConstructTree;
import org.example.ch04.tree.TreeNode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
 * 序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，
 * 同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
 *
 * 请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，
 * 你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
 *
 * 提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。
 * 你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
 */
public class Codec {

    private final String NONE = "None";
    private String resultStr="";

    public static void main(String[] args) {
        Codec codec = new Codec();

        TreeNode treeNode = ConstructTree.constructTree(new Integer[]{1,2,3,null,null,4,5});
        String str = codec.serialize(treeNode);
        System.out.println("序列化："+str);

        TreeNode treeNode1=codec.deserialize("1,2,None,None,3,4,None,None,5,None,None");
        System.out.println("前序遍历：");
//        ConstructTree.preOrder(treeNode1);
        String preString= codec.preOrder(treeNode1,"");
        System.out.println("前序遍历："+preString);
    }

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        return reserialize(root,"");
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] dataArray = data.split(",");
        List<String> dataList = new LinkedList<String>(Arrays.asList(dataArray));
        return rdeserialize(dataList);
    }

    /**
     * 序列化
     * @param root
     * @param str
     * @return
     */
    public String reserialize(TreeNode root,String str){
        if(str.equals(NONE)){
            return null;
        }
        str += root.getVal();
        str =reserialize(root.right,str);
        str =reserialize(root.left,str);
        return str;
    }

    /**
     * 反序列化
     * @param datalist
     * @return
     */
    public TreeNode rdeserialize(List<String> datalist){
       String str=datalist.get(0);
       if(str.equals(NONE)){
           datalist.remove(0);
           return null;
       }
       TreeNode node = new TreeNode(Integer.valueOf(datalist.get(0)));
       datalist.remove(0);
       node.right = rdeserialize(datalist);
       node.left = rdeserialize(datalist);

        return node;
    }


    //前序遍历
    public String preOrder(TreeNode root,String path){
        //递归的终结条件
        if(root == null){
            return path;
        }
        path += String.valueOf(root.getVal()+",") ;
        //本层逻辑 下探到下一层递归，传入主角
        path=preOrder(root.left,path);
        path=preOrder(root.right,path);

        return path;
    }


    //中序遍历
    public String midOrder(TreeNode root){
        if(root==null){
            return null;
        }
        //本层逻辑 下探到下一层递归，传入主角
        midOrder(root.left);
        resultStr +=String.valueOf(root.getVal());
        System.out.println(resultStr);
        midOrder(root.right);
        return null;
    }
    public String tailOrder(TreeNode root){
        if(root==null){
            return null;
        }

        //tailOrder 下探到下一层递归，传入主角
        tailOrder(root.left);
        resultStr +=String.valueOf(root.getVal());
        tailOrder(root.right);
        System.out.println(resultStr);
        return null;
    }


// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

}
